We consider tractable representations of probability distributions and the polytime operations they support. In particular, we consider a recently proposed arithmetic circuit representation, the Probabilistic Sentential Decision Diagram (PSDD). We show that PSDD supports a polytime multiplication operator, while they do not support a polytime operator for summing-out variables. A polytime multiplication operator make PSDDs suitable for a broader class of applications compared to arithmetic circuits, which do not in general support multiplication. As one example, we show that PSDD multiplication leads to a very simple but effective compilation algorithm for probabilistic graphical models: represent each model factor as a PSDD, and then multiply them.

The novelty is relatively low since the compilation algorithm presented here is very similar to the compilation algorithm for AND/OR Multi-Valued Decision Diagrams (AOMDDs), which are a special case of PSDDs. Theorem 6 follows directly from the similar theorem that already holds for AOMDDs. The multiplication algorithm in section 3 is essentially the same as the one for SDDs, and it is no surprise that it operates in polytime. The main novelty and significance is in the experimental results, which suggest that PSDD compilation is more effective than AOMDD compilation. The paper would be more interesting if it gave a deeper analysis of where these advantages come from.

We consider tractable representations of probability distributions and the polytime operations they support. In particular, we consider a recently proposed arithmetic circuit representation, the Probabilistic Sentential Decision Diagram (PSDD). We show that PSDD supports a polytime multiplication operator, while they do not support a polytime operator for summing-out variables. A polytime multiplication operator make PSDDs suitable for a broader class of applications compared to arithmetic circuits, which do not in general support multiplication. As one example, we show that PSDD multiplication leads to a very simple but effective compilation algorithm for probabilistic graphical models: represent each model factor as a PSDD, and then multiply them.